/**Klasse zum sortieren eines Arrays nach dem Mergesortverfahren
 * 
 * @author Björn Klemm, Gerd Ohlweiler, Anna Macjiewska
 *
 */
public class MergeSort {
	/**Mergesortmethode
	 * 
	 * @param a zusortierendes Array
	 * @return gibt temporäres Array zurück
	 */
    public Object[] mergeSort(Object[] a) {
        Object[] tmpArray = new Object[a.length];
        mergeSort(a, tmpArray, 0, a.length - 1);
        return tmpArray;
    }
    
    /**ergesortmethode
     * 
     * @param a zusortierendes Array
     * @param tmpArray
     * @param left
     * @param right
     */
    private void mergeSort(Object[] a, Object[] tmpArray, int left, int right) {
        if( left < right ) {
            int center = (left + right) / 2;
            mergeSort(a,tmpArray, left, center );
            mergeSort(a,tmpArray, center + 1, right );
            merge(a,tmpArray, left, center + 1, right );
        }
    }
    
    /**ergesortmethode
     * 
     * @param a zusortierendes Array
     * @param tmpArray
     * @param leftPos
     * @param rightPos
     * @param rightEnd
     */
    private void merge(Object[] a, Object[] tmpArray, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        while(leftPos <= leftEnd && rightPos <= rightEnd)
            if(a[leftPos].equals(a[rightPos]))
                tmpArray[tmpPos++] = a[leftPos++];
            else
                tmpArray[tmpPos++] = a[rightPos++];
        
        while(leftPos <= leftEnd)    
            tmpArray[tmpPos++] = a[leftPos++];
        
        while(rightPos <= rightEnd)  
            tmpArray[tmpPos++] = a[rightPos++];

        for(int i = 0; i < numElements; i++, rightEnd--)
            a[rightEnd] = tmpArray[rightEnd];
    }
}
